package com.zp.self.module.level_4_算法练习.算法.动态规划;

public class 力扣_70_爬楼梯 {
    static  int 已调用函数总次数 = 0;
    public static void main(String[] args) {
//        System.out.println(new 力扣_70_爬楼梯().climbStairs3(1));
//        System.out.println(new 力扣_70_爬楼梯().climbStairs3(2));
        System.out.println(new 力扣_70_爬楼梯().climbStairs(3));
        System.out.println(new 力扣_70_爬楼梯().climbStairs(5));
        System.out.println(new 力扣_70_爬楼梯().climbStairs(8));
        System.out.println(new 力扣_70_爬楼梯().climbStairs(10));
        System.out.println(new 力扣_70_爬楼梯().climbStairs(20));

    }
    /**
     题目：假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
     每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

     示例 1：
     输入：n = 2
     输出：2
     解释：有两种方法可以爬到楼顶。
     1. 1 阶 + 1 阶
     2. 2 阶

     示例 2：
     输入：n = 3
     输出：3
     解释：有三种方法可以爬到楼顶。
     1. 1 阶 + 1 阶 + 1 阶
     2. 1 阶 + 2 阶
     3. 2 阶 + 1 阶

     分析：【P 💘】
     1：递归--  结果超出时间限制
     首先想到能否递归   --  递归转while
     //总结规律：斐波拉契数列
     //1 1
     //2 2
     //3 3
     //4 5
     //5 8
     //n 阶梯  =  fun(n-1) +fun(n-2) 典型的 斐波拉契数列

     2：数组记录前面每一次的值

     3：动态规划：while变量记录前面两个值

     边界值 & 注意点：
     1.
     **/
    public int climbStairs(int n) {
        //解法3： 动态规划：while变量记录前面两个值
        if(n==1 || n==2) return n;
        int stepN_1=2,stepN_2=1,current=stepN_1;
        while (n-->2){
            current = stepN_1+stepN_2;
            stepN_2 = stepN_1;
            stepN_1 = current;
        }
        return current;

        //1：递归--  结果超出时间限制
       /* if(n == 1 || n == 2) return n;
        String s = "当前调用：fun(" + n + ")=" + "fun(" + (n - 1) + ") + " + "fun(" + (n - 2) + ")"+ "已调用函数总次数:"+(++已调用函数总次数);
        System.out.println(s);
        return climbStairs(n-1)+climbStairs(n-2);*/
    }


    //解法2：数组记录上一次
    public int climbStairs2(int n) {
        //暂不实现，跟两个遍历记录差不多
        return 0;
    }

    //解法3：while变量记录前面两个值
    public int climbStairs3(int n) {
        if(n == 1 || n == 2) return n;
        int proPro = 1;
        int pro = 2;
        int i = 3;
        while (i<=n){
            int sumN = pro+proPro;
            proPro = pro;
            pro = sumN;
            i++;
        }
        return pro;
    }
}
